#include "../tools.h"


struct DListNode{
    int key, val;
    DListNode *nxt, *pre;
    DListNode(int _key = -1, int _val = -1): key(_key), val(_val), nxt(nullptr), pre(nullptr){}
};
void show(DListNode *head){
    while(head != nullptr){
        cout << head->val << " ";
        head = head->nxt;
    }
    cout << endl;
}
class LRUCache {
private:
    unordered_map<int, DListNode*> dict;
    DListNode *head, *tail;
    int _size, _capacity;
public:
    LRUCache(int capacity) {
        _size = 0;
        _capacity = capacity;
        head = new DListNode();
        tail = new DListNode();
        head->nxt = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        if(dict.count(key) == 0) return -1;
        auto p = dict[key];
        // remove p
        p->pre->nxt = p->nxt;
        p->nxt->pre = p->pre;
        // insert head
        head->nxt->pre = p;
        p->nxt = head->nxt;

        head->nxt = p;
        p->pre = head;
        return p->val;
    }
    
    void put(int key, int value) {
        if(get(key) != -1) {
            dict[key]->val = value;
            return;
        }
        // full
        if(_capacity == _size){
            // remove tail
            auto ptail = tail->pre;
            ptail->nxt->pre = ptail->pre;
            ptail->pre->nxt = ptail->nxt;
            dict.erase(ptail->key);     // 先删 dict，再删除 node
            delete ptail;               // 
            --_size;
        }
        // insert head
        auto node = new DListNode(key, value);
        head->nxt->pre = node;
        node->nxt = head->nxt;

        head->nxt = node;
        node->pre = head;
        dict[key] = node;
        ++_size;

    }
};



int main(int argc, char const *argv[])
{
    
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;
    cache.put(3, 3);
    cout << cache.get(2) << endl;
    cache.put(4, 4);
    cout << cache.get(1) << endl;
    cout << cache.get(3) << endl;
    cout << cache.get(4) << endl;
    

    return 0;
}
